//==============================================================================
//
//        DCircle - the circular buffer collection in the ofc-library
//
//               Copyright (C) 2003  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2005-01-31 06:44:29 $ $Revision: 1.5 $
//
//==============================================================================

#include "ofc/DCircle.h"


#if _INTERFACE_

#include "ofc/config.h"

#include "ofc/DStackable.h"
#include "ofc/DQueuable.h"

//
// The circular buffer collection stores objects in an circular buffer that can grow. 
// Objects can be read by an index, which can be negative for accessing elements from 
// the end. This collection can be used for implementing a queue (FIFO) or a stack (LIFO).
//

@interface DCircle : Object <DStackable,DQueuable>
{
@private
  id            *_objects;  // the stored objects
  long           _size;     // the size of the buffer
  long           _first;    // the first element in the buffer (or -1 for empty)
  long           _next;     // the next element in the buffer
}
#endif


@implementation DCircle


#if _PRIVATE_

static long nextIndex(long index, long size)
{
  index++;
  if (index >= size)
  {
    index = 0;
  }
  
  return index;
}

static long prevIndex(long index, long size)
{
  if (index <= 0)
  {
    index = size;
  }
  index--;
  
  return index;
}

#endif
  

//// Constructors

//
// Initialise to an empty buffer
//
// @return the object
//

- (DCircle *) init
{
  [self init :1];

  return self;
}

//
// Initialise to a circular buffer with an initial size
//
// @param size     the size of the buffer
//
// @return the object
//

- (DCircle *) init :(long) size
{
  [super init];

  if (size < 1)
  {
    WARNING(DW_INVALID_ARG, "size");
    size = 1;
  }
    
  _size = size;
    
  _objects = (id *) objc_malloc(sizeof(id) * _size);
  
  {
    long walk;
    
    for (walk = 0; walk < _size; walk++)
    {
      _objects[walk] = nil;
    }
  }

  _first = -1;
  _next  = 0;
  
  return self;
}


//// Copy related methods

//
// Deepen a copy of the buffer
//
// @return the object
//

- deepen
{
  id *origin = _objects;
  
  [super deepen];
  
  _objects = (id *) objc_malloc(sizeof(id) * _size);
  
  {
    long walk;
    
    for (walk = 0; walk < _size; walk++)
    {
      if (origin[walk] != nil)
      {
        _objects[walk] = [origin[walk] copy];
      }
    }
  }
  
  return self;
}


//// Destructor

//
// Free the buffer, not the stored objects
//
// @return the object
//

- shallowFree
{
  {
    long walk;

    for (walk = 0; walk < _size; walk++)
    {
      _objects[walk] = nil;
    }
  }
  
  objc_free(_objects);
  
  return [super free];
}

//
// (Deep) free the buffer (incl. the stored objects)
//
// @return the object
//

- free
{
  long walk;

  for (walk = 0; walk <_size; walk++)
  {
    if (_objects[walk] != nil)
    {
      [_objects[walk] free];
    }
  }

  return [self shallowFree];
}


//// Member methods

//
// Return the size of the buffer
//
// @return the size
//

- (long) size
{
  return _size;
}

//
// Set the size for the buffer
//
// @param size       the new, larger size
//
// @return the object
//

- (DCircle *) size :(long) size
{
  if (size > _size)
  {
    long next = 0;
    long walk = 0;
    
    id *origin = _objects;
    
    _objects = (id *) objc_malloc(sizeof(id) * size);
    
    while (walk < size)
    {
      _objects[walk++] = nil;
    }
    
    if (_first >= 0)
    {
      walk = _first;
      
      do
      {
        _objects[next] = origin[walk];
        
        next = nextIndex(next,  size);
        walk = nextIndex(walk, _size);
      }
      while (walk != _next);
      
      _first = 0;
      _next  = next;
    }

    objc_free(origin);

    _size = size;
  }
  else
  {
    WARNING(DW_INVALID_ARG, "size");
  }
  
  return self;
}

//
// Return the number of stored objects
// 
// @return the length
// 

- (long) length
{
  long length = 0;
  
  if (_first < 0)
  {
    length = 0;
  }
  else if (_first < _next)
  {
    length = _next - _first;
  }
  else
  {
    length = _next - _first + _size;
  }
  
  return length;
}

//
// Check if the buffer is empty
// 
// @return is it ?
// 

- (BOOL) isEmpty
{
  return (_first < 0);
}

//
// Check if the buffer is full
// 
// @return is it ?
// 

- (BOOL) isFull
{
  return ((_first >= 0) && (_first == _next));
}


//// Index methods

//
// Check if an index is valid
//
// @param index   the index
//
// @return is it valid ?
//

- (BOOL) isValid :(long) index
{
  if (index < 0)
  {
    index = ([self length] + index);
  }
  
  return ((index >= 0) && (index < [self length]));
}

//
// Return a reference to the indexth object
//
// @param index      the index
//
// @return the object (or nil if invalid index)
//

- (id) get :(long) index
{
  id obj = nil;
  
  if ([self isValid :index])
  {
    if (index < 0)
    {
      index = [self length] + index;
    }
    
    index += _first;
    
    if (index >= _size)
    {
      index -= _size;
    }
    
    obj = _objects[index];
  }
  else
  {
    WARNING(DW_ARG_OUT_RANGE, "index");
  }
  
  return obj;
}


//// Stack/LIFO methods

//
// Push an object on the stack (LIFO)
//
// @param obj      the object to be pushed
//
// @return success (or buffer full)
//

- (BOOL) push :(id) obj
{
  BOOL ok = YES;
  
  if (_first < 0)
  {
    _objects[0] = obj;
    _first      = 0;
    _next       = nextIndex(0, _size);
  }
  else
  {
    if (_first != _next)
    {
      _objects[_next] = obj;

      _next = nextIndex(_next, _size);
    }
    else
    {
      ok = NO;
    }
  }
  
  return ok;
}

//
// Pop an object from the stack (LIFO)
//
// @return the object (or nil if empty)
//

- (id) pop
{
  id obj = nil;
  
  if (_first >= 0)
  {
    _next = prevIndex(_next, _size);
    
    obj = _objects[_next];
    
    _objects[_next] = nil;

    if (_first == _next)
    {
      _first = -1;
    }
  }
  
  return obj;
}
    
//
// Return the object on top of the stack (LIFO)
// (without changing the top of the stack)
//
// @return the object (or nil if empty)
//

- (id) tos
{
  id obj = nil;
  
  if (_first >= 0)
  {
    long prev = prevIndex(_next, _size);
    
    obj = _objects[prev];
  }
  
  return obj;
}


//// Queue/FIFO Methods

//
// Put an object in the queue (FIFO)
//
// @param obj      the object 
//
// @return success (or buffer full)
//

- (BOOL) enqueue :(id) obj
{
  return [self push :obj];
}

//
// Get an object from the queue (FIFO)
//
// @param obj      the object 
//
// @return the object (or nil for buffer empty)
//

- (id) dequeue 
{
  id obj = nil;
  
  if (_first >= 0)
  {
    obj = _objects[_first];
    
    _objects[_first] = nil;

    _first = nextIndex(_first, _size);

    if (_first == _next)
    {
      _first = -1;
    }
  }
  
  return obj;
}


//// Selector methods

//
// Perform a selector on each object in the circular buffer, 
// starting from the first item in the buffer
//
// @param sel      the selector
//
// @return the object
//

- (DCircle *) each :(SEL) sel
{
  if (_first >= 0)
  {
    long walk = _first;
    
    do
    {
      if (_objects[walk] != nil)
      {
        [_objects[walk] perform :sel];
      }
    
      walk = nextIndex(walk, _size);
    }
    while (walk != _next);
  }
  
  return self;
}

//
// Perform a selector on each object in the circular buffer,
// starting from the last item in the buffer
//
// @param sel      the selector
//
// @return the object
//

- (DCircle *) reach :(SEL) sel
{
  if (_first >= 0)
  {
    long walk = _next;

    do
    {
      walk = prevIndex(walk, _size);
      
      if (_objects[walk] != nil)
      {
        [_objects[walk] perform :sel];
      }
    }
    while (walk != _first);
  }
  
  return self;
}

@end

/*==========================================================================*/
